原题地址：只出现一次的数字 II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
不考虑空间复杂度
与 前一题 类似，不考虑空间复杂度的话，我们也可以利用辅助存储。只是这一次其它元素出现了3次，需要第三次出现才删除，所以改为用Map辅助，方便记录元素出现次数。
具体实现代码如下：
/**
* @param {number[]} nums
* @return {number}
*/
const singleNumber1 = function(nums) {
let map = new Map();
for (let i = 0; i < nums.length; i ++) {
// 获取元素出现次数
let count = map.get(nums[i]);
if (count === 1) {
// 出现过一次，将出现次数改为2
map.set(nums[i], 2);
} else if (count === 2) {
// 已经出现过两次，从map中删除
map.delete(nums[i]);
} else {
// 加入map，记录它出现过一次
map.set(nums[i], 1);
}
}
// map中只剩下出现过一次的元素，转为数组获取
return [...map][0][0];
};
测试：
let start = new Date();
const test = singleNumber1;
console.log(test([2,2,3,2])); // 3
console.log(test([0,1,0,1,0,1,99])); // 9
console.log(new Date().getTime() - start.getTime()); // 3
时间复杂度： 一次遍历，时间复杂度为$O(N)$
空间复杂度： 需要一个辅助map，最多存储数组中三分之一的元素，所以空间复杂度为$O(\frac{1}{3}N)=O(N)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Sep 30,2019